In digital communications systems, data that is to be transmitted is often encoded to increase spectral efficiency or to improve resistance to interference or both. For example, in an asymmetric digital subscriber line (ADSL) digital communications system, for each tone being transmitted, a transmitter can choose a symbol from a set of 22 to 215 possible symbols, depending upon the number of bits (bits=2 to bits=15) carried in the tone. Furthermore, the ADSL technical standards can permit the use of a 4-D 16 state trellis code to improve system performance. The trellis code can be used to encode the two least significant bits of every constellation (tone) while the remaining bits are left uncoded. At a receiver, a Viterbi algorithm can be used to optimally decode the two least significant bits and then the decoded information can be provided to a slicer to permit processing of the higher bits in the tone.
An initial step in the Viterbi algorithm involves the computation of Euclidean distances between a received point (representing the tone) and the closest point in each of four 2-D constellation subsets (cosets). Additionally, to process the higher bits in the tone, the slicer also needs to find the closest valid constellation point that belongs to the coset predicted by the Viterbi algorithm.
A commonly used solution computes the Euclidean distance between the received point and each point in the constellation. This method ensures that the correct answer is found in each case. Furthermore, the computation of the Euclidean distance for each point in the constellation can make the finding of the closest valid constellation point a trivial matter. This solution ensures that the optimum answer is found.
A variant of the above solution involves the use of an “infinite grid” which overlays the constellation and is a superset of the constellation. The use of the infinite grid can simplify the computation of the Euclidean distances between the received point and the points in the constellation, since varying boundary conditions do not have to be considered.
One disadvantage of the prior art is that since the number of points in a constellation can vary from 4 (2 bits −>22 constellation points) to 32768 (15 bits −>215 constellation points), the computation of the Euclidean distances from the received point to each point in the constellation can consume a considerable amount of time. Furthermore, when the constellation size is large, it may not be possible for the computation of the Euclidean distances to complete within an amount of time allotted for the decoding of the received tone.
A second disadvantage of the prior art is that the amount of time to compute the Euclidean distances can vary with the number of constellation points. This can result in an unpredictable decoding time. The unpredictable decoding time can lead to undesirable performance.
A third disadvantage of the prior art is that the use of the infinite grid is not valid since the constellations are finite in size. The use of an infinite grid can lead to decoding errors, especially when the constellation sizes are small (a small number of bits per tone). The decoding errors can result in unacceptable system performance.